﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using UFPE.CIn.Abc.Primality.Util;
using System.Diagnostics;

namespace UFPE.CIn.Abc.Primality.Algorithms
{
    public class AKS : BaseAlgorithm
    {
        private static AKS instance;

        public static AKS Instance
        {
            get
            {
                if (instance == null)
                {
                    instance = new AKS();
                }

                return instance;
            }
        }

        public long[] Fatorar(long val)
        {
            if (val == 1) return new long[] { 1 }; ;

            List<long> fatores = new List<long>();

            long testar = val;
            long mult;

            do
            {
                long encontrado = FatorPrimo(testar);

                if (encontrado == 1) break;

                fatores.Add(encontrado);

                mult = 1;
                foreach (long item in fatores)
                {
                    mult *= item;
                }

                testar = val / mult;
            } while (mult != val);

            //Console.Write("\b\b\n");

            return fatores.ToArray();
        }

        public long FatorPrimo(long rm1)
        {
            long maiorFator;
            long valorInicial = rm1;

            while (true)
            {
                //Console.WriteLine(Math.Sqrt(valorInicial));
                for (maiorFator = (long)Math.Floor(Math.Sqrt(valorInicial)); valorInicial % maiorFator != 0; maiorFator--) ;

                //Console.WriteLine(maiorFator);
                if (BailliePSW.Instance.IsPrime(maiorFator))
                {
                    //Console.Write(maiorFator + ", ");
                    return maiorFator;
                }
                else if (maiorFator == 1)
                {
                    //Console.Write(rm1 + ", ");
                    return rm1;
                }
                else
                {
                    //Console.WriteLine("NaoPrimo");
                    valorInicial = maiorFator;
                }
            }
        }

        public override bool Helper(BigInteger thisVal)
        {
            long val = Convert.ToInt64(thisVal.ToString());

            if (IsPerfectPower(val))
            {
                //Console.WriteLine("Caiu PP");
                return false;
            }
            //Console.WriteLine("Passou PP");

            double log2 = Math.Log(val, 2);

            long r = calcularR(val);

            Console.WriteLine(r);

            if (r == -1) { return false; }
            if (r == val) { return true; }

            long limite = (long)Math.Floor(2 * Math.Sqrt(r) * log2);

            for (long i = 1; i <= limite; i++)
            {
                //Console.WriteLine(i);
                //Stopwatch swTemp = Stopwatch.StartNew();
                Poly polyMod = new Poly(r);
                polyMod.coeficientes[r] = 1;
                polyMod.coeficientes[0] = -1;

                Poly fixedRightSide = new Poly(val);
                fixedRightSide.coeficientes[val] = 1;
                fixedRightSide.coeficientes[0] = i;

                Poly valRightSide = new Poly(0);
                valRightSide.coeficientes[0] = val;

                Poly leftSide = new Poly(i, 1);

                //swTemp.Stop();
                //Console.WriteLine(swTemp.ElapsedMilliseconds + "ms instanciando");
                //swTemp = Stopwatch.StartNew();

                Poly verifyEquality = (fixedRightSide % polyMod) % valRightSide;

                //swTemp.Stop();
                //Console.WriteLine(swTemp.ElapsedMilliseconds + "ms tirando modulo do lado direito");
                //swTemp = Stopwatch.StartNew();

                Poly modPow = (leftSide % polyMod) % valRightSide;
                for (long j = 0; j < val; j++)
                {
                    modPow = modPow * leftSide;
                    modPow = (leftSide % polyMod) % valRightSide;
                }

                //swTemp.Stop();
                //Console.WriteLine(swTemp.ElapsedMilliseconds + "ms fazendo modpow");

                if (modPow != verifyEquality)
                {
                    return false;
                }
            }
            return true;
        }


        public long calcularR(long val)
        {
            long r = 2;
            int iterador = 0;
            int iteradorMax = BigInteger.primesBelow1000000.Length;
            double log2 = Math.Log(val, 2);
            BigInteger valBI = val;

            while (r < val)
            {
                if (Gcd(val, r) != 1)
                {
                    //Console.WriteLine("Caiu GCD");
                    return -1;
                }

                // Testando se r eh primo
                // So precisa testar se iterador >= a quantidade de primos na lista dos menores que 1000000
                bool isRPrime = true;

                if (iterador >= iteradorMax)
                {
                    isRPrime = TrialDivision.Instance.IsPrime(r);
                }

                if (isRPrime)
                {
                    long[] factors = Fatorar(r - 1);
                    long q = factors.Max();

                    if ((q >= 4 * Math.Sqrt(r) * log2)
                        && (valBI.modPow((r - 1) / q, r) != 1))
                    {
                        break;
                    }
                }

                if (iterador < iteradorMax)
                {
                    r = BigInteger.primesBelow1000000[++iterador];
                }
                else
                {
                    r++;
                }
            }

            return r;
        }


        //public long calcularR(long val)
        //{
        //    double log2 = Math.Log(val, 2);
        //    long log22n = (long) Math.Ceiling(4 * log2 * log2);

        //    bool encontrou = false;

        //    long r = 2;
        //    while (!encontrou)
        //    {
        //        if (IsValidR(r, log22n, val))
        //        {
        //            break;
        //        }
        //        r++;
        //    }

        //    return r;
        //}

        //private bool IsValidR(long r, long max, long n)
        //{           
        //    for (long k = 1; k <= max; k++)
        //    {
        //        long val = n;

        //        val = val % r;
        //        for (long i = 0; i < k; i++)
        //        {
        //            val *= n;
        //            val = val % r;
        //        }

        //        if (val == 1)
        //        {
        //            return false;
        //        }
        //    }
        //    return true;
        //}

        public static bool IsPerfectPower(long n)
        {
            //long a = 2;

            //double b;

            //do
            //{
            //    b = Math.Pow(i, (1D / a));
            //    if (Math.Floor(b) == Math.Ceiling(b))
            //    {
            //        return true;
            //    }
            //    a++;
            //} while (b >= 2);

            //return false;

            long b = 2;

            double log10n = Math.Log10(n);
            double log102 = Math.Log10(2);

            long k = (long)(log10n / log102);
            double a=0;
            long aLong = 0;
            while (b <= k)
            {
                //b cannot be bigger than k
                long c = (long)Math.Ceiling((log10n / log102) / b);
                a = Math.Pow(2, c); // assign guess value for a
                while (Math.Pow(a, b) > n)
                {
                    double d = (double)(((b - 1) * a + n / Math.Pow(a, (b - 1))) / b); //Apply Integer Newton’s Method
                    aLong = (long)Math.Floor(d);
                    a = aLong; // adjust a
                }
                
                if (n == Math.Pow(a, b) && new BigInteger(aLong).modPow(b,aLong) == new BigInteger(n).modPow(1, aLong))
                { // if n is a perfect power .
                    Console.WriteLine(a + "^" + b + " == " + n + " == " + Math.Pow(a, b) + ", 0 == " + new BigInteger(Convert.ToInt64(a)).modPow(b, Convert.ToInt64(a)));
                    return true;
                }
                else
                {
                    b = b + 1;
                }
            }
            if (n == Math.Pow(a, b) && new BigInteger(aLong).modPow(b, aLong) == new BigInteger(n).modPow(1, aLong))
            {
                Console.WriteLine(a + "^" + b);
                return true; //n is not a perfect power .
            }
            return false;
        }

        public long Gcd(long x, long y)
        {
            long g = y;

            while (x != 0)
            {
                g = x;
                x = y % x;
                y = g;
            }

            return g;
        }

        // Codigo Baseado em: 
        // LI, Hua. The Analysis and Implementation of the AKS Algorithm and
        // Its Improvement Algorithms. Technical Report. University of Bath,
        // July, 2007
        public static long Euler(long r)
        {
            long euler = 1;

            for (long p = 2; p * p <= r; p += 2)
            {
                if (r % p == 0)
                {
                    euler *= p - 1;
                    r /= p;
                    while (r % p == 0)
                    {
                        euler *= p;
                        r /= p;
                    }
                }

                if (p == 2)
                {
                    p--;
                }
            }

            long ret = euler;

            if (r == 1)
            {
                return ret;
            }

            return ret * (r - 1);
        }

        public override string AlgorithmName
        {
            get
            {
                return "AKS";
            }
        }

        public override long Threshold
        {
            get
            {
                return 32771;
            }
        }
    }
}
